// OD2022Q2考试题 [正则表达式/栈] 报文解压缩
// 题解 https://my.oschina.net/jamesview/blog/5464608
//为了提升数据传输的效率，会对传输的报文进行压缩处理。输入一个压缩后的报文，请返回它解压后的原始报文。
//压缩规则：n [str]，表示方括号内部的 str 正好重复 n 次。注意 n 为正整数（0 < n
//<= 100），str 只包含小写英文字母， 不考虑异常情况。 输入压缩后的报文：
// 1）不考虑无效的输入，报文没有额外的空格，方括号总是符合格式要求的；
// 2）原始报文不包含数字，所有的数字只表示重复的次数 n ，例如不会出现像 5b 或 3
// [8] 的输入； 解压后的原始报文 1）原始报文长度不会超过 1000，不考虑异常的情况
//输入 3[k]2[mn]
//输出 kkkmnmn
// k 重复3次，mn 重复2次，最终得到 kkkmnmn
//输入 3[m2[c]]
//输出 mccmccmcc
// m2[c] 解压缩后为 mcc，重复三次为 mccmccmcc”

#include <bits/stdc++.h>
using namespace std;

#define PF(...)  // printf(__VA_ARGS__)

// 3[m2[n2[v]2[x]]p]
// 21[abc]
vector<string> getMatch(const string& str) {
  std::smatch match;
  std::regex reg("[0-9]+[[a-z]+]");
  vector<string> res;
  for (string tmp = str; regex_search(tmp, match, reg);
       tmp = match.suffix().str()) {
    for (auto ma : match) {
      res.push_back(ma.str());
    }
  }
  return res;
}

string compressMsg_regex(const string& str) {
  vector<string> vtTmp = getMatch(str);
  string sTmp(str);
  while (vtTmp.size() > 0) {
    for (auto brk : vtTmp) {
      size_t spos = brk.find("[");
      size_t epos = brk.find("]");
      int cnt = atoi(brk.substr(0, spos).c_str());
      string fold = brk.substr(spos + 1, epos - spos - 1);
      string unfold;
      for (int i = 0; i < cnt; i++) {
        unfold += fold;
      }
      PF("%s, %d, %s\n", brk.c_str(), brk.size(), unfold.c_str());
      sTmp.replace(sTmp.find(brk), brk.size(), unfold);
    }
    vtTmp = getMatch(sTmp);
  }
  return sTmp;
}

// 33[mm]41[wq]
// 01234567890123
string compressMsg_stack(const string& src) {
  stack<string> stkNum;  // 12
  stack<string> stkMsg;  // [ aa ]
  for (size_t i = 0; i < src.length();) {
    char ch = src[i];
    string stmp;
    if (isalpha(ch)) {
      while (i < src.length() && isalpha(src[i])) stmp += src[i++];
      stkMsg.push(stmp);
    } else if (isdigit(ch)) {
      while (i < src.length() && isdigit(src[i])) stmp += src[i++];
      stkNum.push(stmp);
    } else if (ch == '[') {
      stkMsg.push("[");
      i++;
    } else if (ch == ']') {
      while (!stkMsg.empty() && stkMsg.top() != "[") {
        stmp = stkMsg.top() + stmp;
        stkMsg.pop();
      }
      if (!stkMsg.empty()) stkMsg.pop();  // pop '['
      int nCnt = 1;
      if (!stkNum.empty()) {
        nCnt = stoi(stkNum.top());
        stkNum.pop();
      }
      string sDup;  // 复制n份
      while (nCnt--) sDup += stmp;
      stkMsg.push(sDup);
      i++;
    }
  }
  PF("%d, %s\n", stkMsg.size(), stkMsg.top().c_str());
  string res;
  while (!stkMsg.empty()) {
    res = stkMsg.top() + res;
    stkMsg.pop();
  }
  return res;
}

int main() {
  string res;
  string in;
  in = "3[m2[n2[v]2[x]]p]";
  res = compressMsg_regex(in);
  printf("%s\n", res.c_str());
  in = "aa3[mr]";
  res = compressMsg_regex(in);
  printf("%s\n", res.c_str());
  in = "a";
  res = compressMsg_regex(in);
  printf("%s\n", res.c_str());
  in = "3[q]";
  res = compressMsg_regex(in);
  printf("%s\n", res.c_str());

  in = "3[m2[n2[v]2[x]]p]";
  res = compressMsg_stack(in);
  printf("%s\n", res.c_str());
  in = "aa3[mr]";
  res = compressMsg_stack(in);
  printf("%s\n", res.c_str());
  in = "a";
  res = compressMsg_stack(in);
  printf("%s\n", res.c_str());
  in = "3[q]";
  res = compressMsg_stack(in);
  printf("%s\n", res.c_str());

  return 0;
}
